Search results for "state-pair graph"

showing 2 items of 2 documents

Extremal minimality conditions on automata

2012

AbstractIn this paper we investigate the minimality problem of DFAs by varying the set of final states. In other words, we are interested on how the choice of the final states can affect the minimality of the automata. The state-pair graph is a useful tool to investigate such a problem. The choice of a set of final states for the automaton A defines a coloring of the closed components of the state-pair graph and the minimality of A corresponds to a property of these colored components. A particular attention is devoted to the analysis of some extremal cases such as, for example, the automata that are minimal for any choice of the subset of final states F from the state set Q of the automato…

Discrete mathematicsTheoryofComputation_COMPUTATIONBYABSTRACTDEVICESNested wordSettore INF/01 - InformaticaGeneral Computer Sciencestate-pair graph of automataminimality automataTimed automatonω-automatonNonlinear Sciences::Cellular Automata and Lattice GasesTheoretical Computer ScienceMobile automatonCombinatoricsTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESDFA minimizationContinuous spatial automatonAutomata theoryQuantum finite automataComputer Science::Formal Languages and Automata TheoryComputer Science(all)MathematicsTheoretical Computer Science
researchProduct

Some Remarks on Automata Minimality

2011

It is well known that the minimization problem of deterministic finite automata (DFAs) is related to the indistinguishability notion of states (cf. [HMU00]). Indeed, a well known technique to minimize a DFA, essentially, consists in finding pairs of states that are equivalent (or indistinguishable), namely pairs of states (p,q) such that it is impossible to assert the difference between p and q only by starting in each of the two states and asking whether or not a given input string leads to a final state. Since, in the testing states equivalence, the notion of initial state is irrelevant, some of the main techniques for the minimization of automata, such as Moore’s algorithm [Moo56] and Ho…

Set (abstract data type)Discrete mathematicsDeterministic finite automatonSettore INF/01 - InformaticaRegular languageCayley graphString (computer science)state-pair graph uniformly minimal automataState (functional analysis)Equivalence (measure theory)Computer Science::Formal Languages and Automata TheoryAutomatonMathematics
researchProduct